package com.kami.leetcode.code_202301;

/**
 * @Description Array
 * @Date 2023/1/8 11:26
 **/
public class Array {
    /**
     * @Description 35. 搜索插入位置 二分查找
     * @Date 2023/1/8 11:31
     **/
    public int searchInsert(int[] nums, int target) {
        if (nums[0] >= target) {
            return 0;
        }
        if (nums[nums.length - 1] == target) {
            return nums.length - 1;
        }
        if (nums[nums.length - 1] < target) {
            return nums.length;
        }

        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                if (mid < nums.length - 1 && nums[mid + 1] >= target) {
                    return mid+1 ;
                }
                left = mid + 1;
            } else {
                // num[mid] > target
                if (mid > 0 && nums[mid - 1] <= target) {
                    if (nums[mid - 1] == target) {
                        return mid-1;
                    }
                    return mid;
                }
                right = mid - 1;
            }
        }
        return -1;
    }

    /**
     * @Description 66. 加一
     * @Date 2023/1/8 13:05
     **/
    public int[] plusOne(int[] digits) {
        boolean allNine = true;
        for (int num:digits) {
            if (num != 9){
                allNine = false;
                break;
            }
        }
        if (allNine) {
            int[] res = new int[digits.length+1];
            res[0] = 1;
            return res;
        }
        int take = 1;
        int last = digits.length -1;
        while (take == 1){
            if (digits[last] == 9){
                digits[last] = 0;
            }else {
                digits[last] += 1;
                take = 0;
            }
            last--;
        }
        return digits;
    }
}
